home *** CD-ROM | disk | FTP | other *** search
/ Mac-Source 1994 July / Mac-Source_July_1994.iso / C and C++ / Entertainment / MacMud / Mud 4.0 / otable.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-03-16  |  4.1 KB  |  183 lines  |  [TEXT/tefi]
  1. #include <stdio.h>
  2. #include <string.h>
  3.  
  4. #include "lint.h"
  5. #include "config.h"
  6. #include "interpret.h"
  7. #include "object.h"
  8. #include "rc.h"
  9.  
  10. /*
  11.  * Object name hash table.  Object names are unique, so no special
  12.  * problems - like stralloc.c.  For non-unique hashed names, we need
  13.  * a better package (if we want to be able to get at them all) - we
  14.  * cant move them to the head of the hash chain, for example.
  15.  *
  16.  * Note: if you change an object name, you must remove it and reenter it.
  17.  */
  18.  
  19. char * xalloc();
  20.  
  21. /*
  22.  * hash table - list of pointers to heads of object chains.
  23.  * Each object in chain has a pointer, next_hash, to the next object.
  24.  * OTABLE_SIZE is in config.h, and should be a prime, probably between
  25.  * 100 and 1000.  You can have a quite small table and still get very good
  26.  * performance!  Our database is 8Meg; we use about 500.
  27.  */
  28.  
  29. static struct object ** obj_table = 0;
  30.  
  31. void init_otable()
  32. {
  33.     int x;
  34.     obj_table = (struct object **)
  35.             xalloc(sizeof(struct object *) * OTABLE_SIZE);
  36.  
  37.     for (x=0; x<OTABLE_SIZE; x++)
  38.         obj_table[x] = 0;
  39. }
  40.  
  41. /*
  42.  * Object hash function, ripped off from stralloc.c.
  43.  */
  44.  
  45. static int ObjHash(s)
  46. char * s;
  47. {
  48.     return hashstr(s, 100, OTABLE_SIZE);
  49. }
  50.  
  51. /*
  52.  * Looks for obj in table, moves it to head.
  53.  */
  54.  
  55. static int obj_searches = 0, obj_probes = 0, objs_found = 0;
  56.  
  57. static struct object * find_obj_n(s)
  58. char * s;
  59. {
  60.     struct object * curr, *prev;
  61.  
  62.     int h = ObjHash(s);
  63.  
  64.     curr = obj_table[h];
  65.     prev = 0;
  66.  
  67.     obj_searches++;
  68.  
  69.     while (curr) {
  70.         obj_probes++;
  71.         if (!strcmp(curr->name, s)) { /* found it */
  72.         if (prev) { /* not at head of list */
  73.             prev->next_hash = curr->next_hash;
  74.             curr->next_hash = obj_table[h];
  75.             obj_table[h] = curr;
  76.             }
  77.         objs_found++;
  78.         return(curr);    /* pointer to object */
  79.         }
  80.         prev = curr;
  81.         curr = curr->next_hash;
  82.         }
  83.     
  84.     return(0); /* not found */
  85. }
  86.  
  87. /*
  88.  * Add an object to the table - can't have duplicate names.
  89.  */
  90.  
  91. static int objs_in_table = 0;
  92.  
  93. void enter_object_hash(ob)
  94. struct object * ob;
  95. {
  96.     struct object * s;
  97.     int h = ObjHash(ob->name);
  98.  
  99.     s = find_obj_n(ob->name);
  100.     if (s) {
  101.         if (s != ob)
  102.         fatal("Duplicate object \"%s\" in object hash table",
  103.                 ob->name);
  104.         else
  105.         fatal("Entering object \"%s\" twice in object table",
  106.                 ob->name);
  107.     }
  108.         if (ob->next_hash)
  109.         fatal("Object \"%s\" not found in object table but next link not null",
  110.             ob->name);
  111.     ob->next_hash = obj_table[h];
  112.     obj_table[h] = ob;
  113.     objs_in_table++;
  114.     return;
  115. }
  116.  
  117. /*
  118.  * Remove an object from the table - generally called when it
  119.  * is removed from the next_all list - i.e. in destruct.
  120.  */
  121.  
  122. void remove_object_hash(ob)
  123. struct object *ob;
  124. {
  125.     struct object * s;
  126.     int h = ObjHash(ob->name);
  127.  
  128.     s = find_obj_n(ob->name);
  129.  
  130.     if (s != ob)
  131.         fatal("Remove object \"%s\": found a different object!",
  132.             ob->name);
  133.     
  134.     obj_table[h] = ob->next_hash;
  135.     ob->next_hash = 0;
  136.     objs_in_table--;
  137.     return;
  138. }
  139.  
  140. /*
  141.  * Lookup an object in the hash table; if it isn't there, return null.
  142.  * This is only different to find_object_n in that it collects different
  143.  * stats; more finds are actually done than the user ever asks for.
  144.  */
  145.  
  146. static int user_obj_lookups = 0, user_obj_found = 0;
  147.  
  148. struct object * lookup_object_hash(s)
  149. char * s;
  150. {
  151.     struct object * ob = find_obj_n(s);
  152.     user_obj_lookups++;
  153.     if (ob) user_obj_found++;
  154.     return(ob);
  155. }
  156.  
  157. /*
  158.  * Print stats, returns the total size of the object table.  All objects
  159.  * are in table, so their size is included as well.
  160.  */
  161.  
  162. static char sbuf[100];
  163.  
  164. int show_otable_status(verbose)
  165.     int verbose;
  166. {
  167.     if (verbose) {
  168.     add_message("\nObject name hash table status:\n");
  169.     add_message("------------------------------\n");
  170.     sprintf(sbuf, "%.2f", objs_in_table / (float) OTABLE_SIZE);
  171.     add_message("Average hash chain length               %s\n", sbuf);
  172.     sprintf(sbuf, "%.2f", (float)obj_probes / obj_searches);
  173.     add_message("Searches/average search length       %d (%s)\n",
  174.             obj_searches, sbuf);
  175.     add_message("External lookups succeeded (succeed) %d (%d)\n",
  176.             user_obj_lookups, user_obj_found);
  177.     }
  178.     add_message("hash table overhead\t\t\t %8d\n",
  179.         OTABLE_SIZE * sizeof(struct object *));
  180.     return (OTABLE_SIZE * sizeof(struct object *) +
  181.         objs_in_table * sizeof(struct object));
  182. }
  183.